#include <iostream>
using namespace std;

struct Node
{
    int _val;
    int _height;
    Node *_left;
    Node *_right;
};

class AvlTree
{
public:
    AvlTree() {}
    AvlTree(int val)
        : _root(new Node())
    {
        _root->_val = val;
        _root->_height = 1;
    }
    // 插入结点
    bool count(int val){
        Node* cur=_root;
        while(cur){
            if(val<cur->_val){
                cur=cur->_left;
            }
            else if(val>cur->_val){
                cur=cur->_right;
            }
            else if(val==cur->_val){
                return true;
            }
        }
        return false;
    }
    void insert(int val)
    {
        _root = insertNode(_root, val);
    }
    // 删除结点
    void del(int val)
    {
        _root = delNode(_root, val);
    }
    // 遍历树
    void inOrder()
    {
        inorder(_root);
        cout << endl;
    }
    void preOrder()
    {
        preorder(_root);
        cout << endl;
    }
    void postOrder()
    {
        postorder(_root);
        cout << endl;
    }
    ~AvlTree()
    {
        clean(_root);
    }

private:
    // 创建新结点
    Node *newNode(int val)
    {
        Node *node = new Node();
        node->_val = val;
        node->_height = 1;
        return node;
    }

    int getHeight(Node *node)
    {
        if (!node)
            return 0;
        return node->_height;
    }
    // 获取平衡因子
    int getBalance(Node *node)
    {
        return getHeight(node->_left) - getHeight(node->_right);
    }
    // 左旋函数
    Node *leftRoate(Node *root)
    {
        // 1.当前结点的右子树会作为新树的根节点
        // 2.当前结点root会作为新树根节点的左子树
        // 如果新根结点原来有左子树，则原来的左子树作为旧根结点的右子树
        Node *newRoot = root->_right;
        Node *tem = newRoot->_left;
        newRoot->_left = root;
        root->_right = tem;
        // 更新树高
        root->_height = 1 + max(getHeight(root->_left), getHeight(root->_right));
        newRoot->_height = 1 + max(getHeight(root->_left), getHeight(root->_right));
        return newRoot;
    }

    // 右旋函数
    Node *rightRoate(Node *root)
    {
        Node *newRoot = root->_left;
        Node *tem = newRoot->_right;
        newRoot->_right = root;
        root->_left = tem;
        // 更新树高
        root->_height = 1 + max(getHeight(root->_left), getHeight(root->_right));
        newRoot->_height = 1 + max(getHeight(root->_left), getHeight(root->_right));
        return newRoot;
    }
    // 插入新节点并调整平衡
    Node *insertNode(Node *node, int val)
    {
        if (node == nullptr)
        {
            return newNode(val);
        }
        if (val < node->_val)
        {
            node->_left = insertNode(node->_left, val);
        }
        else if (val > node->_val)
        {
            node->_right = insertNode(node->_right, val);
        }
        else
        {
            return node;
        }
        // 更新树高
        node->_height = 1 + max(getHeight(node->_left), getHeight(node->_right));
        // 获取平衡因子调整平衡
        int balance = getBalance(node);
        // LL失衡
        if (balance > 1 && (getBalance(node->_left) > 0))
        {
            return rightRoate(node);
        }
        // LR失衡
        if (balance > 1 && (getBalance(node->_right) > 0))
        {
            node->_left = leftRoate(node->_left);
            return rightRoate(node);
        }
        // RR失衡
        if (balance < -1 && (getBalance(node->_right) < 0))
        {
            return leftRoate(node);
        }
        // RL失衡
        if (balance < -1 && (getBalance(node->_left) < 0))
        {
            node->_right = rightRoate(node->_right);
            return leftRoate(node);
        }
        return node;
    }

    Node *delNode(Node *node, int val)
    {
        if (node == nullptr)
        {
            return node;
        }
        if (val < node->_val)
        {
            node->_left = delNode(node->_left, val);
        }
        else if (val > node->_val)
        {
            node->_right = delNode(node->_right, val);
        }
        else if (val == node->_val)
        {
            if (node->_left == nullptr && node->_right == nullptr)
            {
                Node *tem = node;
                node = nullptr;
                delete tem;
            }
            else if (node->_left != nullptr && node->_right == nullptr)
            {
                Node *tem = node;
                node = node->_left;
                delete tem;
            }
            else if (node->_left == nullptr && node->_right != nullptr)
            {
                Node *tem = node;
                node = node->_right;
                delete tem;
            }
            else if (node->_left != nullptr && node->_right != nullptr)
            {
                Node *cur = node->_right;
                while (cur->_left)
                {
                    cur = cur->_left;
                }
                node->_val = cur->_val;
                node->_right = delNode(node->_right, cur->_val);
            }
        }
        if(node==nullptr){
            return node;
        }
        //调整
        // 更新树高
        node->_height = 1 + max(getHeight(node->_left), getHeight(node->_right));
        // 获取平衡因子调整平衡
        int balance = getBalance(node);
        // LL失衡
        if (balance > 1 && (getBalance(node->_left) >= 0))
        {
            return rightRoate(node);
        }
        // LR失衡
        if (balance > 1 && (getBalance(node->_right) > 0))
        {
            node->_left = leftRoate(node->_left);
            return rightRoate(node);
        }
        // RR失衡
        if (balance < -1 && (getBalance(node->_right) <= 0))
        {
            return leftRoate(node);
        }
        // RL失衡
        if (balance < -1 && (getBalance(node->_left) < 0))
        {
            node->_right = rightRoate(node->_right);
            return leftRoate(node);
        }
        return node;
    }

    void inorder(Node *node)
    {
        if (node == nullptr)
            return;
        inorder(node->_left);
        cout << node->_val << " ";
        inorder(node->_right);
    }

    void preorder(Node *node)
    {
        if (node == nullptr)
            return;
        cout << node->_val << " ";
        preorder(node->_left);
        preorder(node->_right);
    }
    void postorder(Node *node)
    {
        if (node == nullptr)
            return;
        postorder(node->_left);
        postorder(node->_right);
        cout << node->_val << " ";
    }
    void clean(Node *node)
    {
        if (node == nullptr)
            return;
        clean(node->_left);
        clean(node->_right);
        delete node;
    }

private:
    Node *_root = nullptr;
};

int main()
{
    AvlTree t;
    t.insert(1);
    t.insert(2);
    t.insert(3);
    t.insert(4);
    t.insert(5);
    t.insert(6);
    t.insert(7);
    t.insert(8);
    t.insert(9);
    t.insert(10);
    cout<<t.count(7)<<endl;
    t.inOrder();
    t.preOrder();
    t.postOrder();
    t.del(4);
    t.del(7);
    cout<<t.count(7)<<endl;
    t.inOrder();
    t.preOrder();
    t.postOrder();
    return 0;
}
